package mylab.starters.dag.graph;

import com.google.common.base.Preconditions;
import com.google.common.collect.Sets;

import java.util.List;
import java.util.Set;

import cn.hutool.core.collection.CollUtil;
import lombok.NonNull;
import mylab.base.foundation.lang.StringIdName;
import mylab.starters.dag.graph.impl.BaseEdge;
import mylab.starters.dag.utils.DagUtil;

/**
 * DAG:Directed acyclic graph
 */
public interface Graph extends StringIdName {

    /**
     * 顶点的集合
     */
    Set<Vertex> getVertices();

    /**
     * 边的集合
     */
    Set<Edge> getEdges();

    default int size() {
        return getVertices().size();
    }

    /**
     * 添加顶点
     */
    default Graph addVertex(@NonNull Vertex vertex) {
        vertex.setGraph(this);
        getVertices().add(vertex);

        vertex.getDependentVertices().forEach(v -> {
            getEdges().add(new BaseEdge(v, vertex));
        });
        vertex.getAdjacentVertices().forEach(v -> {
            getEdges().add(new BaseEdge(vertex, v));
        });

        return this;
    }

    /**
     * 添加边
     */
    default Graph addEdge(@NonNull Edge edge) {
        getEdges().add(edge);
        edge.getFrom().adjacent(edge.getTo());

        getVertices().add(edge.getFrom());
        getVertices().add(edge.getTo());
        return this;
    }

    default Graph addVertices(@NonNull Vertex... vertices) {
        Sets.newHashSet(vertices).forEach(this::addVertex);
        return this;
    }

    default Graph addVertices(@NonNull Set<Vertex> vertices) {
        vertices.forEach(this::addVertex);
        return this;
    }

    default Graph addEdges(@NonNull Edge... edges) {
        Sets.newHashSet(edges).forEach(this::addEdge);
        return this;
    }

    default Graph addEdges(@NonNull Set<Edge> edges) {
        edges.forEach(this::addEdge);
        return this;
    }

    /**
     * 查找开始顶点
     */
    default Set<Vertex> getBeginVertices() {
        Set<Vertex> result = Sets.newHashSet();
        getVertices().forEach(vertex -> {
            if (CollUtil.isEmpty(vertex.getDependentVertices())) {
                result.add(vertex);
            }
        });
        return result;
    }

    /**
     * 拓扑排序是将DAG图中的所有节点排成一个线性序列，使得对于每一条有向边(u, v)，节点u在序列中都出现在节点v的前面
     */
    default List<Vertex> topologicalSort() {
        return DagUtil.topologicalSort(this);
    }

    /**
     * 检查DAG图有无形成环
     * 使用深度优先搜索（DFS）来检查环的存在
     */
    default boolean hasCycle() {
        return DagUtil.hasCycle(getVertices());
    }


    default void check() {
        DagUtil.printDagPath(this);
        boolean isAcyclic = !hasCycle();
        Preconditions.checkState(isAcyclic, "DAG must be acyclic");
    }
}